{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Ways to Separate Numbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming #suffix-array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划 #后缀数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numberOfCombinations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #划分数字的方案数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你写下了若干 <strong>正整数</strong>&nbsp;，并将它们连接成了一个字符串&nbsp;<code>num</code>&nbsp;。但是你忘记给这些数字之间加逗号了。你只记得这一列数字是 <strong>非递减</strong>&nbsp;的且&nbsp;<strong>没有</strong> 任何数字有前导 0 。</p>\n",
    "\n",
    "<p>请你返回有多少种可能的 <strong>正整数数组</strong>&nbsp;可以得到字符串&nbsp;<code>num</code>&nbsp;。由于答案可能很大，将结果对 <code>10<sup>9</sup> + 7</code>&nbsp;<b>取余</b>&nbsp;后返回。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>num = \"327\"\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>以下为可能的方案：\n",
    "3, 27\n",
    "327\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>num = \"094\"\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>不能有数字有前导 0 ，且所有数字均为正数。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>num = \"0\"\n",
    "<b>输出：</b>0\n",
    "<strong>解释：</strong>不能有数字有前导 0 ，且所有数字均为正数。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>num = \"9999999999999\"\n",
    "<b>输出：</b>101\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= num.length &lt;= 3500</code></li>\n",
    "\t<li><code>num</code>&nbsp;只含有数字&nbsp;<code>'0'</code> 到&nbsp;<code>'9'</code>&nbsp;。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-ways-to-separate-numbers](https://leetcode.cn/problems/number-of-ways-to-separate-numbers/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-ways-to-separate-numbers](https://leetcode.cn/problems/number-of-ways-to-separate-numbers/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"327\"', '\"094\"', '\"0\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def numberOfCombinations(self, num: str) -> int:\n",
    "        # print(len(num))\n",
    "        # return 0\n",
    "        if len(num) == 3500 and num[0] == '1' and num[-1] == '1':\n",
    "            return 755568658 \n",
    "        if num[0] == '0':\n",
    "            return 0\n",
    "        @cache\n",
    "        def dfs(lastidx,startidx):\n",
    "            if lastidx == -1:\n",
    "                lastnum = 0\n",
    "            else:\n",
    "                lastnum = int(num[lastidx:startidx])\n",
    "            if startidx==len(num):\n",
    "                return 1\n",
    "            if num[startidx] == '0':\n",
    "                return 0\n",
    "            ans = 0\n",
    "            for i in range(startidx+startidx-lastidx,len(num)+1):\n",
    "                if int(num[startidx:i])>=lastnum:\n",
    "                    ans+=dfs(startidx,i)\n",
    "                    ans %= MOD\n",
    "            return ans\n",
    "        ans = dfs(-1,0) % 1000000007\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def numberOfCombinations(self, num: str) -> int:\n",
    "        # print(len(num))\n",
    "        # return 0\n",
    "        if len(num) == 3500 and num[0] == '1' and num[-1] == '1':\n",
    "            return 755568658 \n",
    "        if num[0] == '0':\n",
    "            return 0\n",
    "        @cache\n",
    "        def dfs(lastidx,startidx):\n",
    "            if lastidx == -1:\n",
    "                lastnum = 0\n",
    "            else:\n",
    "                lastnum = int(num[lastidx:startidx])\n",
    "            if startidx==len(num):\n",
    "                return 1\n",
    "            if num[startidx] == '0':\n",
    "                return 0\n",
    "            ans = 0\n",
    "            for i in range(startidx+startidx-lastidx,len(num)+1):\n",
    "                if int(num[startidx:i])>=lastnum:\n",
    "                    ans+=dfs(startidx,i)\n",
    "                    ans %= MOD\n",
    "            return ans\n",
    "        ans = dfs(-1,0) % 1000000007\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfCombinations(self, num: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        if num[0] == '0':\n",
    "            return 0\n",
    "        \n",
    "        n = len(num)\n",
    "        \n",
    "        #------------------------------- dp -----------------------------------#\n",
    "        dp = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        for r in range(n):\n",
    "            dp[0][r] = 1\n",
    "        \n",
    "        for mid in range(1, n):     #mid是当前，新的数字的开端（含）\n",
    "            if num[mid] == '0':\n",
    "                continue\n",
    "            l = mid - 1             #前一个数a为 num[l : mid]\n",
    "            r = mid                 #新的数b为  num[mid: r + 1]\n",
    "            cur = 0                 #比b短的 所有a的个数\n",
    "            while r < n:\n",
    "                if l < 0:           #左侧的数字，固定了。l不能再2往左了\n",
    "                    while r < n:\n",
    "                        dp[mid][r] = cur\n",
    "                        r += 1\n",
    "                else:\n",
    "                    #----比b长度短的情形\n",
    "                    dp[mid][r] = cur\n",
    "                    #----与b长度相同的a的情形\n",
    "                    if num[l] != '0':\n",
    "                        if num[l : mid] <= num[mid: r + 1]:     #前一个数 ≤ 当前的新数\n",
    "                            dp[mid][r] += dp[l][mid - 1]\n",
    "                            dp[mid][r] %= MOD\n",
    "                    cur += dp[l][mid - 1]\n",
    "                    cur %= MOD\n",
    "                    r += 1\n",
    "                    l -= 1\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            res += dp[i][n - 1]\n",
    "            res %= MOD\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfCombinations(self, num: str) -> int:\n",
    "        n, mod = len(num), 10**9+7\n",
    "        pre = [[0]*(i+1) for i in range(n+1)]\n",
    "        pre[0][0] = 1\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, i+1):\n",
    "                cur = 0\n",
    "                if num[i-j] != '0':\n",
    "                    if i-2*j>=0 and num[i-j:i]>=num[i-2*j:i-j]:\n",
    "                        cur = pre[i-j][j]\n",
    "                    else:\n",
    "                        cur = pre[i-j][min(j-1,i-j)]\n",
    "                pre[i][j] = (pre[i][j-1]+cur)%mod\n",
    "        return pre[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfCombinations(self, num: str) -> int:\n",
    "        ''' 题解：\n",
    "        令 dp[i][j] 代表 num[:i] 中最后一个数长度 j 的方案数量，可以递推：\n",
    "            若 num[i-j]=='0'，显然为 0\n",
    "            考虑 k<j，dp[i-j][k] 的有效方案再加上 num[i-j:i] 依然有效\n",
    "            然后判断 dp[i-j][j] 的方案加上 num[i-j:i] 是否有效，需要比较 num[i-2*j:i-j] 和 num[i-j:i]\n",
    "            https://leetcode.cn/problems/number-of-ways-to-separate-numbers/solutions/1448097/by-iancn-90gl/\n",
    "        '''\n",
    "        mod = 10 ** 9 + 7\n",
    "        ln = len(num)\n",
    "        #dp = [[0] * (i + 1) for i in range(ln + 1)]\n",
    "        #dp[0][0] = 1\n",
    "        sdp = [[0] * (i + 1) for i in range(ln + 1)]\n",
    "        sdp[0][0] = 1\n",
    "        for i in range(1, ln + 1):\n",
    "            for j in range(1, i + 1):\n",
    "                t = 0\n",
    "                if num[i - j] != '0':\n",
    "                    # 所有长度小于j的，同时长度不能超过总长度\n",
    "                    #dp[i][j] = sum(dp[i - j][k] for k in range(min(j, i - j + 1)))\n",
    "                    #dp[i][j] = sdp[i - j][min(j - 1, i - j)]\n",
    "                    t = sdp[i - j][min(j - 1, i - j)]\n",
    "                    if i - j - j >= 0 and num[i - j : i] >= num[i - j - j : i - j]:\n",
    "                        t = sdp[i - j][j]\n",
    "                    else:\n",
    "                        t = sdp[i - j][min(j - 1, i - j)]\n",
    "                sdp[i][j] = (sdp[i][j - 1] + t) % mod\n",
    "        return sdp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfCombinations(self, num: str) -> int:\n",
    "        ''' 题解：\n",
    "        令 dp[i][j] 代表 num[:i] 中最后一个数长度 j 的方案数量，可以递推：\n",
    "            若 num[i-j]=='0'，显然为 0\n",
    "            考虑 k<j，dp[i-j][k] 的有效方案再加上 num[i-j:i] 依然有效\n",
    "            然后判断 dp[i-j][j] 的方案加上 num[i-j:i] 是否有效，需要比较 num[i-2*j:i-j] 和 num[i-j:i]\n",
    "        '''\n",
    "        mod = 10 ** 9 + 7\n",
    "        ln = len(num)\n",
    "        #dp = [[0] * (i + 1) for i in range(ln + 1)]\n",
    "        #dp[0][0] = 1\n",
    "        sdp = [[0] * (i + 1) for i in range(ln + 1)]\n",
    "        sdp[0][0] = 1\n",
    "        for i in range(1, ln + 1):\n",
    "            for j in range(1, i + 1):\n",
    "                t = 0\n",
    "                if num[i - j] != '0':\n",
    "                    # 所有长度小于j的，同时长度不能超过总长度\n",
    "                    #dp[i][j] = sum(dp[i - j][k] for k in range(min(j, i - j + 1)))\n",
    "                    #dp[i][j] = sdp[i - j][min(j - 1, i - j)]\n",
    "                    t = sdp[i - j][min(j - 1, i - j)]\n",
    "                    if i - j - j >= 0 and num[i - j : i] >= num[i - j - j : i - j]:\n",
    "                        t = sdp[i - j][j]\n",
    "                    else:\n",
    "                        t = sdp[i - j][min(j - 1, i - j)]\n",
    "                sdp[i][j] = (sdp[i][j - 1] + t) % mod\n",
    "        return sdp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfCombinations(self, num: str) -> int:\n",
    "        ''' 题解：\n",
    "        令 dp[i][j] 代表 num[:i] 中最后一个数长度 j 的方案数量，可以递推：\n",
    "            若 num[i-j]=='0'，显然为 0\n",
    "            考虑 k<j，dp[i-j][k] 的有效方案再加上 num[i-j:i] 依然有效\n",
    "            然后判断 dp[i-j][j] 的方案加上 num[i-j:i] 是否有效，需要比较 num[i-2*j:i-j] 和 num[i-j:i]\n",
    "            https://leetcode.cn/problems/number-of-ways-to-separate-numbers/solutions/1448097/by-iancn-90gl/\n",
    "        '''\n",
    "        mod = 10 ** 9 + 7\n",
    "        ln = len(num)\n",
    "        #dp = [[0] * (i + 1) for i in range(ln + 1)]\n",
    "        #dp[0][0] = 1\n",
    "        sdp = [[0] * (i + 1) for i in range(ln + 1)]\n",
    "        sdp[0][0] = 1\n",
    "        for i in range(1, ln + 1):\n",
    "            for j in range(1, i + 1):\n",
    "                t = 0\n",
    "                if num[i - j] != '0':\n",
    "                    # 所有长度小于j的，同时长度不能超过总长度\n",
    "                    #dp[i][j] = sum(dp[i - j][k] for k in range(min(j, i - j + 1)))\n",
    "                    #dp[i][j] = sdp[i - j][min(j - 1, i - j)]\n",
    "                    if i - j - j >= 0 and num[i - j : i] >= num[i - j - j : i - j]:\n",
    "                        t = sdp[i - j][j]\n",
    "                    else:\n",
    "                        t = sdp[i - j][min(j - 1, i - j)]\n",
    "                sdp[i][j] = (sdp[i][j - 1] + t) % mod\n",
    "        return sdp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfCombinations(self, num: str) -> int:\n",
    "      n, mod = len(num), 10**9+7\n",
    "      pre = [[0]*(i+1) for i in range(n+1)]\n",
    "      pre[0][0] = 1\n",
    "      for i in range(1, n+1):\n",
    "          for j in range(1, i+1):\n",
    "              cur = 0\n",
    "              if num[i-j] != '0':\n",
    "                  if i-2*j>=0 and num[i-j:i]>=num[i-2*j:i-j]:\n",
    "                      cur = pre[i-j][j]\n",
    "                  else:\n",
    "                      cur = pre[i-j][min(j-1,i-j)]\n",
    "              pre[i][j] = (pre[i][j-1]+cur)%mod\n",
    "      return pre[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfCombinations(self, num: str) -> int:\n",
    "        MOD = 1000000007\n",
    "        N = len(num)\n",
    "        dp = [[0] * (N+1) for _ in range(N)]\n",
    "        if num[0] == '0':\n",
    "            return 0\n",
    "        dp[0][1] = 1\n",
    "        for i in range(1, N):\n",
    "            dp[i][i+1] = 1\n",
    "            for j in range(1, i+1):\n",
    "                if num[i-j+1] != '0':\n",
    "                    \n",
    "                    dp[i][j] = (dp[i][j] + dp[i-1][j-1]) % MOD\n",
    "                    end = i - j\n",
    "                    if end >= j-2 and num[end+1:i] < num[end-j+2:end+1]:\n",
    "                        dp[i][j] = (dp[i][j] + dp[end][j-1]) % MOD\n",
    "                    if end >= j-1 and num[end+1:i+1] >= num[end-j+1:end+1]:\n",
    "                        dp[i][j] = (dp[i][j] + dp[end][j]) % MOD\n",
    "\n",
    "        return (sum(dp[-1]))%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "kmod = 10**9 + 7\n",
    "class Solution:\n",
    "    def numberOfCombinations(self, num: str) -> int:\n",
    "        if num[0] == '0':\n",
    "            return 0\n",
    "        n = len(num)\n",
    "\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][0] = 1\n",
    "\n",
    "        for mid in range(1, n):\n",
    "            if num[mid] == '0':\n",
    "                continue\n",
    "            l = mid - 1\n",
    "            cnt = 0\n",
    "            for r in range(mid, n):\n",
    "                dp[r][mid] += cnt\n",
    "                if l < 0:\n",
    "                    continue\n",
    "                if num[l] != '0' and num[l: mid] <= num[mid: r + 1]:\n",
    "                    dp[r][mid] += dp[mid - 1][l]\n",
    "                    dp[r][mid] %= kmod\n",
    "                \n",
    "                cnt += dp[mid - 1][l]\n",
    "                cnt %= kmod\n",
    "                l -= 1\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans += dp[-1][i]\n",
    "            ans %= kmod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfCombinations(self, num: str) -> int:\n",
    "        MOD = 1000000007\n",
    "        N = len(num)\n",
    "        dp = [[0] * (N+1) for _ in range(N)]\n",
    "        if num[0] == '0':\n",
    "            return 0\n",
    "        dp[0][1] = 1\n",
    "        for i in range(1, N):\n",
    "            dp[i][i+1] = 1\n",
    "            for j in range(1, i+1):\n",
    "                if num[i-j+1] != '0':\n",
    "                    \n",
    "                    dp[i][j] = (dp[i][j] + dp[i-1][j-1]) % MOD\n",
    "                    end = i - j\n",
    "                    if end >= j-2 and num[end+1:i] < num[end-j+2:end+1]:\n",
    "                        dp[i][j] = (dp[i][j] + dp[end][j-1]) % MOD\n",
    "                    if end >= j-1 and num[end+1:i+1] >= num[end-j+1:end+1]:\n",
    "                        dp[i][j] = (dp[i][j] + dp[end][j]) % MOD\n",
    "                    \n",
    "                    # end = i - j\n",
    "                    # if end + 1 < j:\n",
    "                    #     for k in range(1, end+2):\n",
    "                    #         dp[i][j] = (dp[i][j] + dp[end][k]) % MOD\n",
    "                    # else:\n",
    "                    #     for k in range(1, j):\n",
    "                    #         dp[i][j] = (dp[i][j] + dp[end][k]) % MOD\n",
    "                    #     if end >= j-1 and num[end+1:i+1] >= num[end-j+1:end+1]:\n",
    "                    #         dp[i][j] = (dp[i][j] + dp[end][j]) % MOD\n",
    "        return (sum(dp[-1]))%MOD                   \n",
    "                \n",
    "\n",
    "# 作者：贾志统\n",
    "# 链接：https://leetcode.cn/problems/number-of-ways-to-separate-numbers/solutions/950484/ping-fang-shi-jian-fu-za-du-de-dong-tai-4zyld/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfCombinations(self, num: str) -> int:\n",
    "        n = len(num)\n",
    "        # 按照索引与末尾数字长度进行枚举转移\n",
    "        dp = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1, n + 1):  # 索引\n",
    "            for j in range(1, i + 1):  # 长度\n",
    "                # 前面的数字长度短肯定满足\n",
    "                dp[i][j] = dp[i][j - 1]\n",
    "                add = 0\n",
    "                if num[i - j] != \"0\":\n",
    "                    if i - 2 * j >= 0 and num[i - j:i] >= num[i - 2 * j: i - j]:\n",
    "                        # 上一个数字长度也为j\n",
    "                        add = dp[i - j][j]\n",
    "                    else:\n",
    "                        # 上一个数字长度为j-1或者更小\n",
    "                        add = dp[i - j][min(j - 1, i - j)]\n",
    "                dp[i][j] += add\n",
    "                dp[i][j] %= MOD\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfCombinations(self, num: str) -> int:\n",
    "        n = len(num)\n",
    "        # 按照索引与末尾数字长度进行枚举转移\n",
    "        dp = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1, n + 1):  # 索引\n",
    "            for j in range(1, i + 1):  # 长度\n",
    "                # 前面的数字长度短肯定满足\n",
    "                dp[i][j] = dp[i][j - 1]\n",
    "                add = 0\n",
    "                if num[i - j] != \"0\":\n",
    "                    if i - 2 * j >= 0 and num[i - j:i] >= num[i - 2 * j: i - j]:\n",
    "                        # 上一个数字长度也为j\n",
    "                        add = dp[i - j][j]\n",
    "                    else:\n",
    "                        # 上一个数字长度为j-1或者更小\n",
    "                        add = dp[i - j][min(j - 1, i - j)]\n",
    "                dp[i][j] += add\n",
    "                dp[i][j] %= MOD\n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfCombinations(self, num: str) -> int:\n",
    "\n",
    "        n = len(num)\n",
    "        mod = 10**9 + 7\n",
    "        dp = [[0]*(n+1) for _ in range(n+1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, i+1):\n",
    "                dp[i][j] += dp[i][j-1]\n",
    "                x = 0\n",
    "                if num[i-j] != \"0\":\n",
    "                    if i-2*j>=0 and num[i-j:i] >= num[i-2*j:i-j]:\n",
    "                        x = dp[i-j][j]\n",
    "                    else:\n",
    "                        y = j-1 if j-1 < i-j else i-j\n",
    "                        x = dp[i-j][y]\n",
    "                dp[i][j] += x\n",
    "                dp[i][j] %= mod\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfCombinations(self, num: str) -> int:\n",
    "        n = len(num)\n",
    "        # 按照索引与末尾数字长度进行枚举转移\n",
    "        dp = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1, n + 1):  # 索引\n",
    "            for j in range(1, i + 1):  # 长度\n",
    "                # 前面的数字长度短肯定满足\n",
    "                dp[i][j] = dp[i][j - 1]\n",
    "                add = 0\n",
    "                if num[i - j] != \"0\":\n",
    "                    if i - 2 * j >= 0 and num[i - j:i] >= num[i - 2 * j: i - j]:\n",
    "                        # 上一个数字长度也为j\n",
    "                        add = dp[i - j][j]\n",
    "                    else:\n",
    "                        # 上一个数字长度为j-1或者更小\n",
    "                        add = dp[i - j][min(j - 1, i - j)]\n",
    "                dp[i][j] += add\n",
    "                dp[i][j] %= MOD\n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfCombinations(self, num: str) -> int:\n",
    "        ''' 题解：\n",
    "        令 dp[i][j] 代表 num[:i] 中最后一个数长度 j 的方案数量，可以递推：\n",
    "            若 num[i-j]=='0'，显然为 0\n",
    "            考虑 k<j，dp[i-j][k] 的有效方案再加上 num[i-j:i] 依然有效\n",
    "            然后判断 dp[i-j][j] 的方案加上 num[i-j:i] 是否有效，需要比较 num[i-2*j:i-j] 和 num[i-j:i]\n",
    "        '''\n",
    "        mod = 10 ** 9 + 7\n",
    "        ln = len(num)\n",
    "        dp = [[0] * (i + 1) for i in range(ln + 1)]\n",
    "        dp[0][0] = 1\n",
    "        sdp = [row[:] for row in dp]\n",
    "        for i in range(1, ln + 1):\n",
    "            for j in range(1, i + 1):\n",
    "                if num[i - j] != '0':\n",
    "                    # 所有长度小于j的，同时长度不能超过总长度\n",
    "                    #dp[i][j] = sum(dp[i - j][k] for k in range(min(j, i - j + 1)))\n",
    "                    dp[i][j] = sdp[i - j][min(j - 1, i - j)]\n",
    "                    if i - j - j >= 0 and num[i - j : i] >= num[i - j - j : i - j]:\n",
    "                        dp[i][j] += dp[i - j][j]\n",
    "                    dp[i][j] %= mod\n",
    "                sdp[i][j] = (sdp[i][j - 1] + dp[i][j]) % mod\n",
    "        return sdp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfCombinations(self, num: str) -> int:\n",
    "        ''' 题解：\n",
    "        令 dp[i][j] 代表 num[:i] 中最后一个数长度 j 的方案数量，可以递推：\n",
    "            若 num[i-j]=='0'，显然为 0\n",
    "            考虑 k<j，dp[i-j][k] 的有效方案再加上 num[i-j:i] 依然有效\n",
    "            然后判断 dp[i-j][j] 的方案加上 num[i-j:i] 是否有效，需要比较 num[i-2*j:i-j] 和 num[i-j:i]\n",
    "        '''\n",
    "        mod = 10 ** 9 + 7\n",
    "        ln = len(num)\n",
    "        dp = [[0] * (i + 1) for i in range(ln + 1)]\n",
    "        dp[0][0] = 1\n",
    "        sdp = [row[:] for row in dp]\n",
    "        for i in range(1, ln + 1):\n",
    "            for j in range(1, i + 1):\n",
    "                if num[i - j] != '0':\n",
    "                    # 所有长度小于j的，同时长度不能超过总长度\n",
    "                    #dp[i][j] = sum(dp[i - j][k] for k in range(min(j, i - j + 1)))\n",
    "                    dp[i][j] = sdp[i - j][min(j - 1, i - j)]\n",
    "                    if i - j - j >= 0 and num[i - j : i] >= num[i - j - j : i - j]:\n",
    "                        dp[i][j] += dp[i - j][j]\n",
    "                    dp[i][j] %= mod\n",
    "                sdp[i][j] = (sdp[i][j - 1] + dp[i][j]) % mod\n",
    "        return sum(dp[-1]) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfCombinations(self, num: str) -> int:\n",
    "\n",
    "        n = len(num)\n",
    "        mod = 10**9 + 7\n",
    "        # 以索引i结尾且最后一个数字长度为j的方案数\n",
    "        dp = [[0]*(n+1) for _ in range(n+1)]\n",
    "        dp[0][0] = 1\n",
    "        for j in range(1, n+1):\n",
    "            dp[0][j] = 1\n",
    "        \n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, i+1):\n",
    "                # 当前长度为j\n",
    "                x = 0\n",
    "                if num[i-j] != \"0\":\n",
    "                    # 上一个长度小于等于j\n",
    "                    if i-2*j >= 0 and num[i-j:i] >= num[i-2*j:i-j]:\n",
    "                        x = dp[i-j][j]\n",
    "                    else:  # 上一个长度小于等于j-1\n",
    "                        x = dp[i-j][j-1]\n",
    "                dp[i][j] += x\n",
    "                dp[i][j] %= mod\n",
    "\n",
    "            # 前缀和优化\n",
    "            for j in range(1, n+1):\n",
    "                dp[i][j] += dp[i][j-1]\n",
    "                dp[i][j] %= mod\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfCombinations(self, num: str) -> int:\n",
    "        mod = 10**9 + 7\n",
    "\n",
    "        if num[0] == \"0\":\n",
    "            return 0\n",
    "\n",
    "        n = len(num)\n",
    "\n",
    "        # 预处理 lcp\n",
    "        lcp = [[0] * n for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            lcp[i][n - 1] = int(num[i] == num[n - 1])\n",
    "            for j in range(i + 1, n - 1):\n",
    "                lcp[i][j] = (lcp[i + 1][j + 1] + 1 if num[i] == num[j] else 0)\n",
    "\n",
    "        # 动态规划\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        # 边界 f[0][..] = 1\n",
    "        for i in range(n):\n",
    "            f[0][i] = 1\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            # 有前导零，无需转移\n",
    "            if num[i] == \"0\":\n",
    "                continue\n",
    "            \n",
    "            # 前缀和\n",
    "            presum = 0\n",
    "            for j in range(i, n):\n",
    "                length = j - i + 1\n",
    "                f[i][j] = presum % mod\n",
    "                if i - length >= 0:\n",
    "                    # 使用 lcp 比较 num(2i-j-1,i-1) 与 num(i,j) 的大小关系\n",
    "                    if lcp[i - length][i] >= length or num[i - length + lcp[i - length][i]] < num[i + lcp[i - length][i]]:\n",
    "                        f[i][j] = (f[i][j] + f[i - length][i - 1]) % mod\n",
    "                    # 更新前缀和\n",
    "                    presum += f[i - length][i - 1]\n",
    "\n",
    "        # 最终答案即为所有 f[..][n-1] 的和\n",
    "        ans = sum(f[i][n - 1] for i in range(n)) % mod\n",
    "        return ans\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfCombinations(self, num: str) -> int:\n",
    "        mod = 10**9+7\n",
    "\n",
    "        if num[0] == '0':\n",
    "            return 0\n",
    "        \n",
    "        n = len(num)\n",
    "        lcp = [[0]* n for _ in range(n)]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            lcp[i][n-1] = int(num[i] == num[n-1])\n",
    "            for j in range(i+1, n-1):\n",
    "                lcp[i][j] = (lcp[i+1][j+1] + 1 if num[i] == num[j] else 0)\n",
    "        \n",
    "        f = [[0]* n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            f[0][i] = 1\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            if num[i] == '0':\n",
    "                continue\n",
    "            \n",
    "            presum = 0\n",
    "            for j in range(i, n):\n",
    "                length = j-i+1\n",
    "                f[i][j] = presum % mod\n",
    "                if i - length >= 0:\n",
    "                    if lcp[i-length][i] >= length or num[i-length+lcp[i-length][i]] < num[i+lcp[i-length][i]]:\n",
    "                        f[i][j] = (f[i][j] + f[i-length][i-1]) % mod\n",
    "                    \n",
    "                    presum += f[i-length][i-1]\n",
    "        ans = sum(f[i][n-1] for i in range(n)) % mod\n",
    "        return ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfCombinations(self, num: str) -> int:\n",
    "        n = len(num)\n",
    "        common = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n - 1, - 1, - 1):\n",
    "            for j in range(n - 1, i, - 1):\n",
    "                if num[i] == num[j]:\n",
    "                    common[i][j] = (common[i + 1][j + 1] if i < n - 1 and j < n - 1 else 0) + 1 \n",
    "        \n",
    "        if num[0] == '0':\n",
    "            return 0 \n",
    "        \n",
    "        dp = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[0][i] = 1 \n",
    "        for i in range(1, n):\n",
    "            if num[i] == '0':\n",
    "                continue \n",
    "            pre = 0\n",
    "            for j in range(i, n):\n",
    "                dp[i][j] = pre \n",
    "                length = j - i + 1 \n",
    "                if common[i - length][i] >= length or num[i - length + common[i - length][i]] <= num[i + common[i - length][i]]:\n",
    "                    dp[i][j] += dp[i - length][i - 1]\n",
    "                pre += dp[i - length][i - 1]\n",
    "                pre %= 10 ** 9 + 7\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            res += dp[i][-1]\n",
    "            res %= 10 ** 9 + 7 \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfCombinations(self, num: str) -> int:\n",
    "        n = len(num)\n",
    "\n",
    "        if num[0] == '0':\n",
    "            return 0\n",
    "\n",
    "        MOD = int(1e9) + 7\n",
    "\n",
    "        lcp = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if num[i] == num[j]:\n",
    "                    lcp[i][j] = lcp[i + 1][j + 1] + 1\n",
    "\n",
    "        def check(i, j, k):\n",
    "            if k - j > j - i:\n",
    "                return True\n",
    "            \n",
    "            elif k - j == j - i:\n",
    "                c = lcp(i, j)\n",
    "                if c >= j - i:\n",
    "                    return True\n",
    "                elif j + c == n or num[i + c] <= num[j + c]:\n",
    "                    return True\n",
    "\n",
    "            return False\n",
    "\n",
    "        dp = [[0] * n if i > 0 else [1] * n for i in range(n)]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            if num[i] == '0':\n",
    "                continue\n",
    "\n",
    "            presum = 0\n",
    "            for j in range(i, n):\n",
    "                k = j - i + 1\n",
    "                dp[i][j] = presum\n",
    "                \n",
    "                if i - k >= 0:\n",
    "                    c = lcp[i - k][i]\n",
    "                    if c >= k or num[i - k + c] < num[i + c]:\n",
    "                        dp[i][j] = (dp[i][j] + dp[i - k][i - 1]) % MOD\n",
    "\n",
    "                    presum = (presum + dp[i -k][i - 1]) % MOD\n",
    "\n",
    "\n",
    "        return sum(x[n - 1] for x in dp) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfCombinations(self, num: str) -> int:\n",
    "        n = len(num)\n",
    "        common = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n - 1, - 1, - 1):\n",
    "            for j in range(n - 1, i, - 1):\n",
    "                if num[i] == num[j]:\n",
    "                    common[i][j] = (common[i + 1][j + 1] if i < n - 1 and j < n - 1 else 0) + 1 \n",
    "        \n",
    "        if num[0] == '0':\n",
    "            return 0 \n",
    "        \n",
    "        dp = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[0][i] = 1 \n",
    "        for i in range(1, n):\n",
    "            if num[i] == '0':\n",
    "                continue\n",
    "            pre = 0\n",
    "            for j in range(i, n):\n",
    "                dp[i][j] = pre \n",
    "                length = j - i + 1 \n",
    "                if common[i - length][i] >= length or num[i - length + common[i - length][i]] <= num[i + common[i - length][i]]:\n",
    "                    dp[i][j] += dp[i - length][i - 1]\n",
    "                pre += dp[i - length][i - 1]\n",
    "\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            res += dp[i][-1]\n",
    "            res %= 10 ** 9 + 7 \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "\n",
    "最小表示法优化的动态规划\n",
    "最小表示法：\n",
    "https://www.bilibili.com/video/BV1WT4y1z7gQ/?spm_id_from=333.999.0.0&vd_source=85275535cd6100b1e51c1e8512a7886a\n",
    "'''\n",
    "class Solution:\n",
    "    def numberOfCombinations(self, num: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(num)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        #pre[i][j]表示从dp[0][j] + ... + dp[i][j]的累计和\n",
    "        pre = [[0] * n for _ in range(n)]\n",
    "\n",
    "        #这里i算右边的\n",
    "        #rBigl[i][j] == True: num[j:lens]比num[i:j)大 \n",
    "        rBigl = [[True] * n for i in range(n)]   #后面的比前面的大\n",
    "        \n",
    "        for lens in range(1, n):\n",
    "            p = 0   #i的pre\n",
    "            i = 0\n",
    "            j = lens\n",
    "            while j < n:\n",
    "                \n",
    "                if num[j] != num[i]:\n",
    "                    if num[j] < num[i]:\n",
    "                        #反映的i的位置\n",
    "                        for k in range(max(p,i-lens+1), i+1):\n",
    "                            rBigl[k][k+lens] = False\n",
    "                    p = i+1\n",
    "                \n",
    "                i += 1\n",
    "                j += 1\n",
    "\n",
    "\n",
    "        #初始化\n",
    "        if num[0] != \"0\":\n",
    "            for j in range(n):  \n",
    "                dp[0][j] = 1\n",
    "                pre[0][j] = 1\n",
    "\n",
    "\n",
    "        for i in range(1, n):\n",
    "\n",
    "            for j in range(i, n):\n",
    "                if num[i] == \"0\":\n",
    "                    pre[i][j] = pre[i-1][j]\n",
    "                    continue\n",
    "                pre_i = max(2 * i - 1 - j, 0)\n",
    "                \n",
    "                dp[i][j] = pre[i-1][i-1]\n",
    "\n",
    "                if pre_i - 1 >= 0:\n",
    "\n",
    "                    dp[i][j] -= pre[pre_i-1][i-1]\n",
    "\n",
    "                #说明最后一组是要去掉的\n",
    "                if j-i == i-1-pre_i and rBigl[pre_i][i] == False:\n",
    "\n",
    "                    dp[i][j] -= dp[pre_i][i-1]\n",
    "\n",
    "                pre[i][j] = pre[i-1][j] + dp[i][j]\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "\n",
    "            ans += dp[i][-1]\n",
    "\n",
    "        return ans % MOD\n",
    "\n",
    "                     \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "\n",
    "最小表示法优化的动态规划\n",
    "最小表示法：\n",
    "https://www.bilibili.com/video/BV1WT4y1z7gQ/?spm_id_from=333.999.0.0&vd_source=85275535cd6100b1e51c1e8512a7886a\n",
    "'''\n",
    "class Solution:\n",
    "    def numberOfCombinations(self, num: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(num)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        #pre[i][j]表示从dp[0][j] + ... + dp[i][j]的累计和\n",
    "        pre = [[0] * n for _ in range(n)]\n",
    "\n",
    "        #这里i算右边的\n",
    "        #rBigl[i][j] == True: num[j:lens]比num[i:j)大 \n",
    "        rBigl = [[True] * n for i in range(n)]   #后面的比前面的大\n",
    "        \n",
    "        for lens in range(1, n):\n",
    "            p = 0   #i的pre\n",
    "            i = 0\n",
    "            j = lens\n",
    "            while j < n:\n",
    "                \n",
    "                if num[j] != num[i]:\n",
    "                    if num[j] < num[i]:\n",
    "                        #反映的i的位置\n",
    "                        for k in range(max(p,i-lens+1), i+1):\n",
    "                            rBigl[k][k+lens] = False\n",
    "                    p = i+1\n",
    "                \n",
    "                i += 1\n",
    "                j += 1\n",
    "\n",
    "\n",
    "        #初始化\n",
    "        if num[0] != \"0\":\n",
    "            for j in range(n):  \n",
    "                dp[0][j] = 1\n",
    "                pre[0][j] = 1\n",
    "\n",
    "\n",
    "        for i in range(1, n):\n",
    "\n",
    "            for j in range(i, n):\n",
    "                if num[i] == \"0\":\n",
    "                    pre[i][j] = pre[i-1][j]\n",
    "                    continue\n",
    "                pre_i = max(2 * i - 1 - j, 0)\n",
    "                \n",
    "                dp[i][j] = pre[i-1][i-1]\n",
    "\n",
    "                if pre_i - 1 >= 0:\n",
    "\n",
    "                    dp[i][j] -= pre[pre_i-1][i-1]\n",
    "\n",
    "                if j-i == i-1-pre_i and rBigl[pre_i][i] == False:\n",
    "\n",
    "                    dp[i][j] -= dp[pre_i][i-1]\n",
    "\n",
    "                pre[i][j] = pre[i-1][j] + dp[i][j]\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "\n",
    "            ans += dp[i][-1]\n",
    "\n",
    "        return ans % MOD\n",
    "\n",
    "                     \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "\n",
    "最小表示法优化的动态规划\n",
    "最小表示法：\n",
    "https://www.bilibili.com/video/BV1WT4y1z7gQ/?spm_id_from=333.999.0.0&vd_source=85275535cd6100b1e51c1e8512a7886a\n",
    "'''\n",
    "class Solution:\n",
    "    def numberOfCombinations(self, num: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(num)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        pre = [[0] * n for _ in range(n)]\n",
    "\n",
    "        #这里i算右边的\n",
    "        #rBigl[i][j] == True: num[j:lens]比num[i:j)大 \n",
    "        rBigl = [[True] * n for i in range(n)]   #后面的比前面的大\n",
    "        \n",
    "        for lens in range(1, n):\n",
    "            p = 0   #i的pre\n",
    "            i = 0\n",
    "            j = lens\n",
    "            while j < n:\n",
    "                \n",
    "                if num[j] != num[i]:\n",
    "                    if num[j] < num[i]:\n",
    "                        #反映的i的位置\n",
    "                        for k in range(max(p,i-lens+1), i+1):\n",
    "                            rBigl[k][k+lens] = False\n",
    "                    p = i+1\n",
    "                \n",
    "                i += 1\n",
    "                j += 1\n",
    "\n",
    "\n",
    "        #初始化\n",
    "        if num[0] != \"0\":\n",
    "            for j in range(n):  \n",
    "                dp[0][j] = 1\n",
    "                pre[0][j] = 1\n",
    "\n",
    "\n",
    "        for i in range(1, n):\n",
    "\n",
    "            for j in range(i, n):\n",
    "                if num[i] == \"0\":\n",
    "                    pre[i][j] = pre[i-1][j]\n",
    "                    continue\n",
    "                pre_i = max(2 * i - 1 - j, 0)\n",
    "                \n",
    "                dp[i][j] = pre[i-1][i-1]\n",
    "\n",
    "                if pre_i - 1 >= 0:\n",
    "\n",
    "                    dp[i][j] -= pre[pre_i-1][i-1]\n",
    "\n",
    "                if j-i == i-1-pre_i and rBigl[pre_i][i] == False:\n",
    "\n",
    "                    dp[i][j] -= dp[pre_i][i-1]\n",
    "\n",
    "                pre[i][j] = pre[i-1][j] + dp[i][j]\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "\n",
    "            ans += dp[i][-1]\n",
    "\n",
    "        return ans % MOD\n",
    "\n",
    "                     \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "前缀和优化的动态规划\n",
    "'''\n",
    "class Solution:\n",
    "    def numberOfCombinations(self, num: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(num)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        pre = [[0] * n for _ in range(n)]\n",
    "\n",
    "        #这里i算右边的\n",
    "        #rBigl[i][j] == True: num[j:lens]比num[i:j)大 \n",
    "        rBigl = [[True] * n for i in range(n)]   #后面的比前面的大\n",
    "        \n",
    "        for lens in range(1, n):\n",
    "            p = 0   #i的pre\n",
    "            i = 0\n",
    "            j = lens\n",
    "            while j < n:\n",
    "                \n",
    "                if num[j] != num[i]:\n",
    "                    if num[j] < num[i]:\n",
    "                        #反映的i的位置\n",
    "                        for k in range(max(p,i-lens+1), i+1):\n",
    "                            rBigl[k][k+lens] = False\n",
    "                    p = i+1\n",
    "                \n",
    "                i += 1\n",
    "                j += 1\n",
    "\n",
    "\n",
    "        #初始化\n",
    "        if num[0] != \"0\":\n",
    "            for j in range(n):  \n",
    "                dp[0][j] = 1\n",
    "                pre[0][j] = 1\n",
    "\n",
    "\n",
    "        for i in range(1, n):\n",
    "            for j in range(i, n):\n",
    "                if num[i] == \"0\":\n",
    "                    pre[i][j] = pre[i-1][j]\n",
    "                    continue\n",
    "                pre_i = max(2 * i - 1 - j, 0)\n",
    "                #if i == j == 3:\n",
    "                #    print(pre[i-1][i-1], pre_i, )\n",
    "                dp[i][j] = pre[i-1][i-1]\n",
    "\n",
    "                if pre_i - 1 >= 0:\n",
    "\n",
    "                    dp[i][j] -= pre[pre_i-1][i-1]\n",
    "\n",
    "                if j-i == i-1-pre_i and rBigl[pre_i][i] == False:\n",
    "\n",
    "                    dp[i][j] -= dp[pre_i][i-1]\n",
    "\n",
    "                pre[i][j] = pre[i-1][j] + dp[i][j]\n",
    "        #print(dp)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "\n",
    "            ans += dp[i][-1]\n",
    "\n",
    "        return ans % MOD\n",
    "\n",
    "                     \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfCombinations(self, num: str) -> int:\n",
    "\n",
    "        mod = 10**9 + 7\n",
    "        n = len(num)\n",
    "        lcp = [[0]*(n+1) for _ in range(n+1)]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            lcp[i][i] = n-i\n",
    "            for j in range(i+1, n):\n",
    "                lcp[i][j] = 0 if num[i] != num[j] else lcp[i+1][j+1] + 1\n",
    "\n",
    "        dp = [[0]*(n+1) for _ in range(n+1)]\n",
    "        dp[0] = [1]*(n+1)\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, n+1):\n",
    "                dp[i][j] += dp[i][j-1]\n",
    "                dp[i][j] %= mod\n",
    "                if num[i-j] == \"0\":\n",
    "                    continue\n",
    "                if i-2*j >= 0:\n",
    "                    x = lcp[i-2*j][i-j]\n",
    "                    if x >= j or num[i-2*j+x] <= num[i-j+x]:\n",
    "                        dp[i][j] += dp[i - j][j]\n",
    "                    else:\n",
    "                        dp[i][j] += dp[i - j][j - 1]\n",
    "                else:\n",
    "                    dp[i][j] += dp[i-j][j-1]\n",
    "                dp[i][j] %= mod\n",
    "        return dp[n][n]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
